<!DOCTYPE html>
<html lang="zh-CN">
    <head>
        <meta charset="utf-8">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="robots" content="noodp" />
        <title>关于并查集的一切 - L_B__</title><meta name="referrer" content="no-referrer">
<meta name="description" content="关于并查集的一切"><meta property="og:title" content="关于并查集的一切" />
<meta property="og:description" content="关于并查集的一切" />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" /><meta property="og:image" content="https://acking-you.github.io/logo.png"/><meta property="article:section" content="posts" />
<meta property="article:published_time" content="2022-12-19T00:00:00+00:00" />
<meta property="article:modified_time" content="2022-12-19T00:00:00+00:00" />

<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://acking-you.github.io/logo.png"/>

<meta name="twitter:title" content="关于并查集的一切"/>
<meta name="twitter:description" content="关于并查集的一切"/>
<meta name="application-name" content="FeelIt">
<meta name="apple-mobile-web-app-title" content="FeelIt"><meta name="theme-color" content="#ffffff"><meta name="msapplication-TileColor" content="#da532c"><link rel="canonical" href="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" /><link rel="prev" href="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E4%B8%80%E5%88%87/" /><link rel="next" href="https://acking-you.github.io/posts/chatgp%E6%95%99%E6%88%91%E5%86%85%E5%AD%98%E5%AF%B9%E9%BD%90/" /><link rel="stylesheet" href="/css/page.min.css"><link rel="stylesheet" href="/css/home.min.css"><script type="application/ld+json">
    {
        "@context": "http://schema.org",
        "@type": "BlogPosting",
        "headline": "关于并查集的一切",
        "inLanguage": "zh-CN",
        "mainEntityOfPage": {
            "@type": "WebPage",
            "@id": "https:\/\/acking-you.github.io\/posts\/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87\/"
        },"genre": "posts","keywords": "关于并查集的一切","wordcount":  2287 ,
        "url": "https:\/\/acking-you.github.io\/posts\/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87\/","datePublished": "2022-12-19T00:00:00+00:00","dateModified": "2022-12-19T00:00:00+00:00","publisher": {
            "@type": "Organization",
            "name": "作者"},"author": {
                "@type": "Person",
                "name": "作者"
            },"description": "关于并查集的一切"
    }
    </script></head><body data-header-desktop="auto" data-header-mobile="auto"><script>(window.localStorage && localStorage.getItem('theme') ? localStorage.getItem('theme') === 'dark' : ('auto' === 'auto' ? window.matchMedia('(prefers-color-scheme: dark)').matches : 'auto' === 'dark')) && document.body.setAttribute('theme', 'dark');</script>

        <div id="mask"></div><div class="wrapper"><header class="desktop" id="header-desktop">
    <div class="header-wrapper">
        <div class="header-title">
            <a href="/" title="L_B__">L_B__</a>
        </div>
        <div class="menu">
            <div class="menu-inner"><a class="menu-item" href="/posts/"> 文章 </a><a class="menu-item" href="/tags/"> 标签 </a><a class="menu-item" href="/categories/"> 分类 </a><span class="menu-item delimiter"></span><span class="menu-item search" id="search-desktop">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-desktop">
                        <a href="#" class="search-button search-toggle" id="search-toggle-desktop" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-desktop" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-desktop">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </span><a href="javascript:void(0);" class="menu-item theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div>
        </div>
    </div>
</header><header class="mobile" id="header-mobile">
    <div class="header-container">
        <div class="header-wrapper">
            <div class="header-title">
                <a href="/" title="L_B__">L_B__</a>
            </div>
            <div class="menu-toggle" id="menu-toggle-mobile">
                <span></span><span></span><span></span>
            </div>
        </div>
        <div class="menu" id="menu-mobile"><div class="search-wrapper">
                    <div class="search mobile" id="search-mobile">
                        <input type="text" placeholder="搜索文章标题或内容..." id="search-input-mobile">
                        <a href="#" class="search-button search-toggle" id="search-toggle-mobile" title="搜索">
                            <i class="fas fa-search fa-fw"></i>
                        </a>
                        <a href="#" class="search-button search-clear" id="search-clear-mobile" title="清空">
                            <i class="fas fa-times-circle fa-fw"></i>
                        </a>
                        <span class="search-button search-loading" id="search-loading-mobile">
                            <i class="fas fa-spinner fa-fw fa-spin"></i>
                        </span>
                    </div>
                    <a href="#" class="search-cancel" id="search-cancel-mobile">
                        取消
                    </a>
                </div><a class="menu-item" href="/posts/" title="">文章</a><a class="menu-item" href="/tags/" title="">标签</a><a class="menu-item" href="/categories/" title="">分类</a><div class="menu-item"><a href="javascript:void(0);" class="theme-switch" title="切换主题">
                    <i class="fas fa-adjust fa-fw"></i>
                </a>
            </div></div>
    </div>
</header><div class="search-dropdown desktop">
    <div id="search-dropdown-desktop"></div>
</div>
<div class="search-dropdown mobile">
    <div id="search-dropdown-mobile"></div>
</div><main class="main">
                <div class="container"><div class="toc" id="toc-auto">
            <h2 class="toc-title">目录</h2>
            <div class="toc-content" id="toc-content-auto"></div>
        </div><article class="page single" data-toc="disable"><div class="featured-image"><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center, https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center 1.5x, https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center"
        title="关于并查集的一切" /></div><div class="single-card" data-image="true"><h2 class="single-title animated flipInX">关于并查集的一切</h2><div class="post-meta">
                <div class="post-meta-line"><span class="post-author"><a href="/" title="Author" rel=" author" class="author"><i class="fas fa-user-circle fa-fw"></i>作者</a></span>&nbsp;<span class="post-category">出版于  <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%B9%B6%E6%9F%A5%E9%9B%86/"><i class="far fa-folder fa-fw"></i>数据结构——并查集</a></span></div>
                <div class="post-meta-line"><span><i class="far fa-calendar-alt fa-fw"></i>&nbsp;<time datetime="2022-12-19">2022-12-19</time></span>&nbsp;<span><i class="fas fa-pencil-alt fa-fw"></i>&nbsp;约 2287 字</span>&nbsp;
                    <span><i class="far fa-clock fa-fw"></i>&nbsp;预计阅读 5 分钟</span>&nbsp;</div>
            </div>
            
            <hr><div class="details toc" id="toc-static"  data-kept="">
                    <div class="details-summary toc-title">
                        <span>目录</span>
                        <span><i class="details-icon fas fa-angle-right"></i></span>
                    </div>
                    <div class="details-content toc-content" id="toc-content-static"><nav id="TableOfContents">
  <ul>
    <li><a href="#并查集初识">并查集初识</a>
      <ul>
        <li><a href="#并查集常用术语">「并查集」常用术语</a></li>
        <li><a href="#并查集基本思想">「并查集」基本思想</a></li>
        <li><a href="#并查集的两个实现方式">「并查集」的两个实现方式</a></li>
      </ul>
    </li>
    <li><a href="#quick-find-方式实现并查集">Quick Find 方式实现并查集</a>
      <ul>
        <li><a href="#quick-find工作原理">Quick Find工作原理：</a></li>
        <li><a href="#代码实现与验证">代码实现与验证</a></li>
        <li><a href="#时间复杂度">时间复杂度</a></li>
      </ul>
    </li>
    <li><a href="#quick-union-方式实现并查集">Quick Union 方式实现并查集</a>
      <ul>
        <li><a href="#quick-union的工作原理">Quick Union的工作原理</a></li>
        <li><a href="#为什么-quick-union-比-quick-find-更加高效">为什么 Quick Union 比 Quick Find 更加高效？</a></li>
        <li><a href="#代码实现与验证-1">代码实现与验证</a></li>
        <li><a href="#时间复杂度-1">时间复杂度</a></li>
      </ul>
    </li>
    <li><a href="#按秩合并优化并查集">按秩合并优化并查集</a>
      <ul>
        <li><a href="#视频讲解">视频讲解</a></li>
        <li><a href="#代码实现与验证-2">代码实现与验证</a></li>
      </ul>
    </li>
    <li><a href="#路径压缩优化的并查集">路径压缩优化的并查集</a>
      <ul>
        <li><a href="#视频讲解-1">视频讲解</a></li>
        <li><a href="#代码实现路径压缩按秩合并">代码实现(路径压缩+按秩合并)</a></li>
      </ul>
    </li>
    <li><a href="#综合运用例题">综合运用例题</a>
      <ul>
        <li><a href="#解题代码">解题代码</a></li>
      </ul>
    </li>
  </ul>
</nav></div>
                </div><div class="content" id="content"><h2 id="并查集初识">并查集初识</h2>
<p>如果给你一些顶点，并且告诉你每个顶点的连接关系，你如何才能快速的找出两个顶点是否具有连通性呢？如「图 5. 连通性问题」，该图给出了顶点与顶点之间的连接关系，那么，我们如何让计算机快速定位 (0, 3) , (1, 5), (7, 8) 是否相连呢？此时我们就需要机智的「并查集」数据结构了。很多地方也会称「并查集」为算法，这也没问题。<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/db52ac623466ed844192da58da65cdfd.png"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/db52ac623466ed844192da58da65cdfd.png, https://img-blog.csdnimg.cn/img_convert/db52ac623466ed844192da58da65cdfd.png 1.5x, https://img-blog.csdnimg.cn/img_convert/db52ac623466ed844192da58da65cdfd.png 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/db52ac623466ed844192da58da65cdfd.png"
        title="连通性问题" />「并查集」的主要作用是用来解决网络中的连通性。这里的「网络」可以是计算机的网络，也可以是人际关系的网络等等。例如，你可以通过「并查集」来判定两个人是否来自同一个祖先。</p>
<h3 id="并查集常用术语">「并查集」常用术语</h3>
<ul>
<li>父节点：顶点的直接父亲节点。如「图5. 连通性问题」中，顶点 3 的父节点是 1；顶点 2 的父节点是 0；顶点 9 的父节点是自己本身 9。</li>
<li>根节点：没有父节点的节点，本身可以视为自己的父节点。如「图5. 连通性问题」中，顶点 3 和 2 的根节点都是 0；0 即是自己本身的父节点，也是自己的根节点；顶点 9 的根节点是自己本身 9。</li>
</ul>
<h3 id="并查集基本思想">「并查集」基本思想</h3>
<p><strong>视频内容摘要：</strong></p>
<ol>
<li>如何在计算机中设计出「并查集」数据结构</li>
<li>「并查集」的 <code>find</code> 函数；</li>
<li>「并查集」的 <code>union</code> 函数。</li>
</ol>
<p><a href="https://www.youtube.com/watch?v=EklycxMEQ68" target="_blank" rel="noopener noreffer">视频链接</a></p>
<h3 id="并查集的两个实现方式">「并查集」的两个实现方式</h3>
<ul>
<li>Quick Find 实现方式：它指的是实现「并查集」时，find 函数时间复杂度很低为 O(1)O(1)，但对应的 union 函数就需要承担更多的责任，它的时间复杂度为 O(N)O(N)。</li>
<li>Quick Union 实现方式：它指的是实现「并查集」时，相对于 Quick Find 的实现方式，我们通过降低 union 函数的职责来提高它的效率，但同时，我们也增加了 find 函数的职责。</li>
</ul>
<hr>
<h2 id="quick-find-方式实现并查集">Quick Find 方式实现并查集</h2>
<h3 id="quick-find工作原理">Quick Find工作原理：</h3>
<p><a href="https://youtu.be/OJfFR_sHmBI" target="_blank" rel="noopener noreffer">视频链接</a></p>
<h3 id="代码实现与验证">代码实现与验证</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">class</span> <span class="nc">UnionFind</span><span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
    <span class="kt">int</span><span class="o">*</span> <span class="n">root</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">UnionFind</span><span class="p">(</span><span class="kt">int</span> <span class="n">size</span><span class="p">)</span><span class="o">:</span><span class="n">length</span><span class="p">(</span><span class="n">size</span><span class="p">){</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">size</span><span class="p">];</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">length</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">];</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">merge</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">rootX</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">rootY</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
        <span class="k">if</span><span class="p">(</span><span class="n">rootX</span><span class="o">!=</span><span class="n">rootY</span><span class="p">){</span>
            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">length</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
                <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="n">rootY</span><span class="p">)</span>
                    <span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootX</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">bool</span> <span class="nf">isconnected</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="k">return</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="o">==</span><span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
    <span class="n">UnionFind</span> <span class="n">a</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="mi">5</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">6</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">6</span><span class="p">,</span><span class="mi">7</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">8</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">5</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">7</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">9</span><span class="p">,</span><span class="mi">4</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><h3 id="时间复杂度">时间复杂度</h3>
<table>
<thead>
<tr>
<th></th>
<th>UnionFind 构造函数</th>
<th>find 函数</th>
<th>merge函数</th>
<th>isconnected 函数</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>时间复杂度</strong></td>
<td><em>O</em>(<em>N</em>)</td>
<td><em>O</em>(1)</td>
<td><em>O</em>(<em>N</em>)</td>
<td><em>O</em>(1)</td>
</tr>
</tbody>
</table>
<p>注：<em>N</em> 为「图」中顶点的个数。</p>
<hr>
<h2 id="quick-union-方式实现并查集">Quick Union 方式实现并查集</h2>
<h3 id="quick-union的工作原理">Quick Union的工作原理</h3>
<p><a href="https://www.youtube.com/watch?v=QcDQACEQEsw" target="_blank" rel="noopener noreffer">视频链接</a></p>
<h3 id="为什么-quick-union-比-quick-find-更加高效">为什么 Quick Union 比 Quick Find 更加高效？</h3>
<p>总体来说，Quick Union 是比 Quick Find 更加高效的。为什么呢？</p>
<p><a href="https://www.youtube.com/watch?v=feSr-fiGxw8" target="_blank" rel="noopener noreffer">视频链接</a></p>
<h3 id="代码实现与验证-1">代码实现与验证</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">class</span> <span class="nc">UnionFind</span><span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
    <span class="kt">int</span><span class="o">*</span> <span class="n">root</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">UnionFind</span><span class="p">(</span><span class="kt">int</span> <span class="n">size</span><span class="p">)</span><span class="o">:</span><span class="n">length</span><span class="p">(</span><span class="n">size</span><span class="p">){</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">size</span><span class="p">];</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">length</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span>
        <span class="k">while</span><span class="p">(</span><span class="n">x</span><span class="o">!=</span><span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">]){</span>
            <span class="n">x</span> <span class="o">=</span> <span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">];</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">merge</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">rootX</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">rootY</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
        <span class="k">if</span><span class="p">(</span><span class="n">rootX</span><span class="o">!=</span><span class="n">rootY</span><span class="p">){</span>
            <span class="n">root</span><span class="p">[</span><span class="n">rootY</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootX</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">bool</span> <span class="nf">isconnected</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="k">return</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="o">==</span><span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
    <span class="n">UnionFind</span> <span class="n">a</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="mi">5</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">6</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">6</span><span class="p">,</span><span class="mi">7</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">8</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">5</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">7</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">9</span><span class="p">,</span><span class="mi">4</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><h3 id="时间复杂度-1">时间复杂度</h3>
<table>
<thead>
<tr>
<th></th>
<th>UnionFind 构造函数</th>
<th>find 函数</th>
<th>merge函数</th>
<th>isconnected 函数</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>时间复杂度</strong></td>
<td><em>O</em>(<em>N</em>)</td>
<td><em>O</em>(H)</td>
<td><em>O</em>(H)</td>
<td><em>O</em>(H)</td>
</tr>
</tbody>
</table>
<p>注：<em>N</em> 为「图」中顶点的个数，<em>H</em> 为「树」的高度。</p>
<hr>
<h2 id="按秩合并优化并查集">按秩合并优化并查集</h2>
<p>小伙伴看到这里的时候，我们其实已经实现了 2 种「并查集」。但它们都有一个很大的缺点，这个缺点就是通过 <code>merge</code> 函数连接顶点之后，可能所有顶点连成一条线形成「图 5. 一条线的图」，这就是我们 <code>find</code> 函数在最坏的情况下的样子。那么我们有办法解决吗？</p>
<p>当然，伟大的科学家已经给出了解决方案，就是按秩合并。这里的「秩」可以理解为「秩序」。之前我们在 <code>merge</code> 的时候，我们是随机选择 x 和 y 中的一个根节点/父节点作为另一个顶点的根节点。但是在「按秩合并」中，我们是按照「某种秩序」选择一个父节点。</p>
<p>这里的「秩」指的是每个顶点所处的高度。我们每次 <code>merge</code> 两个顶点的时候，选择根节点的时候不是随机的选择某个顶点的根节点，而是将「秩」大的那个根节点作为两个顶点的根节点，换句话说，我们将低的树合并到高的树之下，将高的树的根节点作为两个顶点的根节点。这样，我们就避免了所有的顶点连成一条线，这就是按秩合并优化的「并查集」。</p>
<p><img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/img_convert/4c2e158208cd32f6edd983d49770bfbb.png"
        data-srcset="https://img-blog.csdnimg.cn/img_convert/4c2e158208cd32f6edd983d49770bfbb.png, https://img-blog.csdnimg.cn/img_convert/4c2e158208cd32f6edd983d49770bfbb.png 1.5x, https://img-blog.csdnimg.cn/img_convert/4c2e158208cd32f6edd983d49770bfbb.png 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/img_convert/4c2e158208cd32f6edd983d49770bfbb.png"
        title="一条线的图" /></p>
<h3 id="视频讲解">视频讲解</h3>
<p><a href="https://www.youtube.com/watch?v=uKeCSXqeigE" target="_blank" rel="noopener noreffer">视频链接</a></p>
<h3 id="代码实现与验证-2">代码实现与验证</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">class</span> <span class="nc">UnionFind</span><span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
    <span class="kt">int</span><span class="o">*</span> <span class="n">root</span><span class="p">;</span>
    <span class="kt">int</span><span class="o">*</span> <span class="n">rank</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">UnionFind</span><span class="p">(</span><span class="kt">int</span> <span class="n">size</span><span class="p">)</span><span class="o">:</span><span class="n">length</span><span class="p">(</span><span class="n">size</span><span class="p">){</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">size</span><span class="p">];</span>
        <span class="n">rank</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">size</span><span class="p">];</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">length</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
            <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span>
        <span class="k">while</span><span class="p">(</span><span class="n">x</span><span class="o">!=</span><span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">]){</span>
            <span class="n">x</span> <span class="o">=</span> <span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">];</span>
        <span class="p">}</span>
        <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">merge</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">rootX</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">rootY</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
        <span class="c1">//高度小的树被高度大的合并，如果高度一致合并后高度增加
</span><span class="c1"></span>        <span class="k">if</span><span class="p">(</span><span class="n">rootX</span><span class="o">!=</span><span class="n">rootY</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">&gt;</span><span class="n">rank</span><span class="p">[</span><span class="n">rootY</span><span class="p">]){</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootY</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootX</span><span class="p">;</span>
            <span class="p">}</span> <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">&lt;</span><span class="n">rank</span><span class="p">[</span><span class="n">rootY</span><span class="p">]){</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootY</span><span class="p">;</span>
            <span class="p">}</span><span class="k">else</span><span class="p">{</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootY</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootX</span><span class="p">;</span>
                <span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">++</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">bool</span> <span class="nf">isconnected</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="k">return</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="o">==</span><span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
    <span class="n">UnionFind</span> <span class="n">a</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="mi">5</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">6</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">6</span><span class="p">,</span><span class="mi">7</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">8</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">5</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">7</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">9</span><span class="p">,</span><span class="mi">4</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><table>
<thead>
<tr>
<th></th>
<th>UnionFind 构造函数</th>
<th>find 函数</th>
<th>merge函数</th>
<th>isconnected 函数</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>时间复杂度</strong></td>
<td><em>O</em>(<em>N</em>)</td>
<td><em>O</em>(logN)</td>
<td><em>O</em>(logN)</td>
<td><em>O</em>(logN)</td>
</tr>
</tbody>
</table>
<p>注：<em>N</em> 为「图」中顶点的个数。</p>
<hr>
<h2 id="路径压缩优化的并查集">路径压缩优化的并查集</h2>
<p>从前面的「并查集」实现方式中，我们不难看出，要想找到一个元素的根节点，需要沿着它的父亲节点的足迹一直遍历下去，直到找到它的根节点为止。如果下次再查找同一个元素的根节点，我们还是要做相同的操作。那我们有没有什么办法将它升级优化下呢？</p>
<p>答案是可以的！如果我们在找到根节点之后，将所有遍历过的元素的父节点都改成根节点，那么我们下次再查询到相同元素的时候，我们就仅仅只需要遍历两个元素就可以找到它的根节点了，这是非常高效的实现方式。那么问题来了，我们如何将所有遍历过的元素的父节点都改成根节点呢？这里就要拿出「递归」算法了。这种优化我们称之为「路径压缩」优化，它是对 <code>find</code> 函数的一种优化。</p>
<h3 id="视频讲解-1">视频讲解</h3>
<p><a href="https://www.youtube.com/watch?v=g1157X1vhdY" target="_blank" rel="noopener noreffer">视频链接</a></p>
<blockquote>
<p>实际路径压缩应该还有一种迭代的方式，此视频未提到。</p>
</blockquote>
<h3 id="代码实现路径压缩按秩合并">代码实现(路径压缩+按秩合并)</h3>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="cp">#include</span> <span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="k">class</span> <span class="nc">UnionFind</span><span class="p">{</span>
<span class="k">private</span><span class="o">:</span>
    <span class="kt">int</span><span class="o">*</span> <span class="n">root</span><span class="p">;</span>
<span class="c1">// 添加了 rank 数组来记录每个顶点的高度，也就是每个顶点的「秩」
</span><span class="c1"></span>    <span class="kt">int</span><span class="o">*</span> <span class="n">rank</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">length</span><span class="p">;</span>
<span class="k">public</span><span class="o">:</span>
    <span class="n">UnionFind</span><span class="p">(</span><span class="kt">int</span> <span class="n">size</span><span class="p">)</span><span class="o">:</span><span class="n">length</span><span class="p">(</span><span class="n">size</span><span class="p">){</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">size</span><span class="p">];</span>
        <span class="n">rank</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">size</span><span class="p">];</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">length</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
            <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">int</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span>
        <span class="c1">//递归方式
</span><span class="c1"></span>        <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">==</span><span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">])</span>
            <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">]</span><span class="o">=</span><span class="n">find</span><span class="p">(</span><span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">]);</span>
        <span class="cm">/*迭代方式
</span><span class="cm">        int cur = x;
</span><span class="cm">        while(cur!=root[cur]){
</span><span class="cm">            root[cur] = root[root[cur]];
</span><span class="cm">            cur = root[cur];
</span><span class="cm">        }
</span><span class="cm">        return cur;*/</span>
    <span class="p">}</span>
    <span class="c1">// 按秩合并优化的 merge 函数
</span><span class="c1"></span>    <span class="kt">void</span> <span class="nf">merge</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">rootX</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">rootY</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
        <span class="c1">//高度小的树被高度大的合并，如果高度一致合并后高度增加
</span><span class="c1"></span>        <span class="k">if</span><span class="p">(</span><span class="n">rootX</span><span class="o">!=</span><span class="n">rootY</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">&gt;</span><span class="n">rank</span><span class="p">[</span><span class="n">rootY</span><span class="p">]){</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootY</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootX</span><span class="p">;</span>
            <span class="p">}</span> <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">&lt;</span><span class="n">rank</span><span class="p">[</span><span class="n">rootY</span><span class="p">]){</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootY</span><span class="p">;</span>
            <span class="p">}</span><span class="k">else</span><span class="p">{</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootY</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootX</span><span class="p">;</span>
                <span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">++</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kt">bool</span> <span class="nf">isconnected</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="k">return</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="o">==</span><span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
    <span class="n">UnionFind</span> <span class="n">a</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="mi">5</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">6</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">6</span><span class="p">,</span><span class="mi">7</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">3</span><span class="p">,</span><span class="mi">8</span><span class="p">);</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="mi">5</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">5</span><span class="p">,</span><span class="mi">7</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">)</span><span class="o">&lt;&lt;</span><span class="sc">&#39; &#39;</span><span class="p">;</span>
    <span class="n">a</span><span class="p">.</span><span class="n">merge</span><span class="p">(</span><span class="mi">9</span><span class="p">,</span><span class="mi">4</span><span class="p">);</span>
    <span class="n">cout</span><span class="o">&lt;&lt;</span><span class="n">a</span><span class="p">.</span><span class="n">isconnected</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="mi">9</span><span class="p">);</span>
<span class="p">}</span>
</code></pre></div><table>
<thead>
<tr>
<th></th>
<th>UnionFind 构造函数</th>
<th>find 函数</th>
<th>merge函数</th>
<th style="text-align:center">isconnected 函数</th>
</tr>
</thead>
<tbody>
<tr>
<td><strong>时间复杂度</strong></td>
<td><em>O</em>(<em>N</em>)</td>
<td><em>O</em>(⍺(<em>N</em>))</td>
<td>O(⍺(N))</td>
<td style="text-align:center"><em>O</em>(⍺(<em>N</em>))</td>
</tr>
</tbody>
</table>
<p>注：<em>N</em> 为「图」中顶点的个数。</p>
<h2 id="综合运用例题">综合运用例题</h2>
<p><a href="https://leetcode-cn.com/problems/number-of-provinces/" target="_blank" rel="noopener noreffer">省份数量</a>
<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/7678bf99f646443089ffd817dd235cbf.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0,size_16,color_FFFFFF,t_70"
        data-srcset="https://img-blog.csdnimg.cn/7678bf99f646443089ffd817dd235cbf.png?x-oss-process=image/watermark%2ctype_ZmFuZ3poZW5naGVpdGk%2cshadow_10%2ctext_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0%2csize_16%2ccolor_FFFFFF%2ct_70, https://img-blog.csdnimg.cn/7678bf99f646443089ffd817dd235cbf.png?x-oss-process=image/watermark%2ctype_ZmFuZ3poZW5naGVpdGk%2cshadow_10%2ctext_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0%2csize_16%2ccolor_FFFFFF%2ct_70 1.5x, https://img-blog.csdnimg.cn/7678bf99f646443089ffd817dd235cbf.png?x-oss-process=image/watermark%2ctype_ZmFuZ3poZW5naGVpdGk%2cshadow_10%2ctext_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0%2csize_16%2ccolor_FFFFFF%2ct_70 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/7678bf99f646443089ffd817dd235cbf.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0,size_16,color_FFFFFF,t_70"
        title="题目描述" /></p>
<h3 id="解题代码">解题代码</h3>
<blockquote>
<p>这效率yyds！<img
        class="lazyload"
        src="/svg/loading.min.svg"
        data-src="https://img-blog.csdnimg.cn/663ab19ace1c45edba4a88110e2405f3.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0,size_16,color_FFFFFF,t_70"
        data-srcset="https://img-blog.csdnimg.cn/663ab19ace1c45edba4a88110e2405f3.png?x-oss-process=image/watermark%2ctype_ZmFuZ3poZW5naGVpdGk%2cshadow_10%2ctext_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0%2csize_16%2ccolor_FFFFFF%2ct_70, https://img-blog.csdnimg.cn/663ab19ace1c45edba4a88110e2405f3.png?x-oss-process=image/watermark%2ctype_ZmFuZ3poZW5naGVpdGk%2cshadow_10%2ctext_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0%2csize_16%2ccolor_FFFFFF%2ct_70 1.5x, https://img-blog.csdnimg.cn/663ab19ace1c45edba4a88110e2405f3.png?x-oss-process=image/watermark%2ctype_ZmFuZ3poZW5naGVpdGk%2cshadow_10%2ctext_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0%2csize_16%2ccolor_FFFFFF%2ct_70 2x"
        data-sizes="auto"
        alt="https://img-blog.csdnimg.cn/663ab19ace1c45edba4a88110e2405f3.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzUwOTQ1NTA0,size_16,color_FFFFFF,t_70"
        title="执行效率" /></p>
</blockquote>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-cpp" data-lang="cpp"><span class="k">class</span> <span class="nc">Solution</span> <span class="p">{</span>
<span class="k">public</span><span class="o">:</span>
    <span class="kt">int</span> <span class="n">findCircleNum</span><span class="p">(</span><span class="n">vector</span><span class="o">&lt;</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;&gt;&amp;</span> <span class="n">isConnected</span><span class="p">)</span> <span class="p">{</span>
        <span class="kt">int</span> <span class="n">n</span> <span class="o">=</span> <span class="n">isConnected</span><span class="p">.</span><span class="n">size</span><span class="p">();</span>
        <span class="n">root</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">n</span><span class="p">];</span>
        <span class="n">rank</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="p">[</span><span class="n">n</span><span class="p">];</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="n">root</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span><span class="p">;</span>
            <span class="n">rank</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="n">cnt</span> <span class="o">=</span> <span class="n">n</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
            <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">i</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">){</span>
                <span class="k">if</span><span class="p">(</span><span class="n">isConnected</span><span class="p">[</span><span class="n">i</span><span class="p">][</span><span class="n">j</span><span class="p">])</span>
                    <span class="n">merge</span><span class="p">(</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">);</span>
            <span class="p">}</span>
        <span class="p">}</span>
        
        <span class="k">return</span> <span class="n">cnt</span><span class="p">;</span>
    <span class="p">}</span>
<span class="k">private</span><span class="o">:</span>
    <span class="kt">int</span><span class="o">*</span> <span class="n">root</span><span class="p">;</span>
    <span class="kt">int</span><span class="o">*</span> <span class="n">rank</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">cnt</span><span class="p">;</span>
    <span class="kt">int</span> <span class="nf">find</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">==</span> <span class="n">x</span><span class="p">)</span>
            <span class="k">return</span> <span class="n">x</span><span class="p">;</span>
        <span class="k">return</span> <span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">]</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">root</span><span class="p">[</span><span class="n">x</span><span class="p">]);</span>
    <span class="p">}</span>
    <span class="kt">void</span> <span class="nf">merge</span><span class="p">(</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">y</span><span class="p">){</span>
        <span class="kt">int</span> <span class="n">rootX</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">x</span><span class="p">);</span>
        <span class="kt">int</span> <span class="n">rootY</span> <span class="o">=</span> <span class="n">find</span><span class="p">(</span><span class="n">y</span><span class="p">);</span>
        <span class="k">if</span><span class="p">(</span><span class="n">rootX</span><span class="o">!=</span><span class="n">rootY</span><span class="p">){</span>
            <span class="k">if</span><span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">&lt;</span><span class="n">rank</span><span class="p">[</span><span class="n">rootY</span><span class="p">])</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootY</span><span class="p">;</span>
            <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">rank</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span><span class="o">&gt;</span><span class="n">rank</span><span class="p">[</span><span class="n">rootY</span><span class="p">])</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootY</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootX</span><span class="p">;</span>
            <span class="k">else</span><span class="p">{</span>
                <span class="n">root</span><span class="p">[</span><span class="n">rootX</span><span class="p">]</span> <span class="o">=</span> <span class="n">rootY</span><span class="p">;</span>
                <span class="n">rank</span><span class="p">[</span><span class="n">rootY</span><span class="p">]</span><span class="o">++</span><span class="p">;</span>
            <span class="p">}</span>
            <span class="c1">//初始有多个集合，一旦合并一次就少一个集合
</span><span class="c1"></span>            <span class="n">cnt</span><span class="o">--</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">};</span>
</code></pre></div></div><div class="post-footer" id="post-footer">
    <div class="post-info"><div class="post-info-tag"><span><a href="/tags/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/">关于并查集的一切</a>
                </span></div><div class="post-info-line"><div class="post-info-mod">
                <span>更新于 2022-12-19</span>
            </div><div class="post-info-mod"></div>
        </div><div class="post-info-share">
            <span><a href="javascript:void(0);" title="分享到 Twitter" data-sharer="twitter" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-title="关于并查集的一切" data-hashtags="关于并查集的一切"><i class="fab fa-twitter fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Facebook" data-sharer="facebook" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-hashtag="关于并查集的一切"><i class="fab fa-facebook-square fa-fw"></i></a><a href="javascript:void(0);" title="分享到 WhatsApp" data-sharer="whatsapp" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-title="关于并查集的一切" data-web><i class="fab fa-whatsapp fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Line" data-sharer="line" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-title="关于并查集的一切"><i class="fab fa-line fa-fw"></i></a><a href="javascript:void(0);" title="分享到 微博" data-sharer="weibo" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-title="关于并查集的一切" data-image="https://img-blog.csdnimg.cn/img_convert/acea126d07748d6630f37b1b481e5d73.png#pic_center"><i class="fab fa-weibo fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Myspace" data-sharer="myspace" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-title="关于并查集的一切" data-description="关于并查集的一切"><i data-svg-src="/lib/simple-icons/icons/myspace.min.svg"></i></a><a href="javascript:void(0);" title="分享到 Blogger" data-sharer="blogger" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-title="关于并查集的一切" data-description="关于并查集的一切"><i class="fab fa-blogger fa-fw"></i></a><a href="javascript:void(0);" title="分享到 Evernote" data-sharer="evernote" data-url="https://acking-you.github.io/posts/%E5%85%B3%E4%BA%8E%E5%B9%B6%E6%9F%A5%E9%9B%86%E7%9A%84%E4%B8%80%E5%88%87/" data-title="关于并查集的一切"><i class="fab fa-evernote fa-fw"></i></a></span>
        </div></div><div class="post-nav"><a href="/posts/%E5%85%B3%E4%BA%8E%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E4%B8%80%E5%88%87/" class="prev" rel="prev" title="关于最小生成树的一切"><i class="fas fa-angle-left fa-fw"></i>Previous Post</a>
            <a href="/posts/chatgp%E6%95%99%E6%88%91%E5%86%85%E5%AD%98%E5%AF%B9%E9%BD%90/" class="next" rel="next" title="chatgpt教我内存对齐，对齐了但没完全对齐？">Next Post<i class="fas fa-angle-right fa-fw"></i></a></div></div>
</div></article></div>
            </main>
            <footer class="footer"><div class="footer-container"><div class="footer-line">由 <a href="https://gohugo.io/" target="_blank" rel="noopener noreffer" title="Hugo 0.86.0">Hugo</a> 强力驱动 | 主题 - <a href="https://github.com/khusika/FeelIt" target="_blank" rel="noopener noreffer" title="FeelIt 1.0.1"><i class="fas fa-hand-holding-heart fa-fw"></i> FeelIt</a>
        </div><div class="footer-line" itemscope itemtype="http://schema.org/CreativeWork"><i class="far fa-copyright fa-fw"></i><span itemprop="copyrightYear">2023</span><span class="author" itemprop="copyrightHolder">&nbsp;<a href="/"></a></span></div>
</div>
</footer>
        </div>

        <div id="fixed-buttons"><a href="#" id="back-to-top" class="fixed-button" title="回到顶部">
                <i class="fas fa-chevron-up fa-fw"></i>
            </a></div><link rel="stylesheet" href="/lib/fontawesome-free/all.min.css"><link rel="stylesheet" href="/lib/animate/animate.min.css"><link rel="stylesheet" href="/lib/katex/katex.min.css"><link rel="stylesheet" href="/lib/katex/copy-tex.min.css"><script src="/lib/autocomplete/autocomplete.min.js"></script><script src="/lib/lunr/lunr.min.js"></script><script src="/lib/lunr/lunr.stemmer.support.min.js"></script><script src="/lib/lunr/lunr.zh.min.js"></script><script src="/lib/lazysizes/lazysizes.min.js"></script><script src="/lib/clipboard/clipboard.min.js"></script><script src="/lib/sharer/sharer.min.js"></script><script src="/lib/katex/katex.min.js"></script><script src="/lib/katex/auto-render.min.js"></script><script src="/lib/katex/copy-tex.min.js"></script><script src="/lib/katex/mhchem.min.js"></script><script>window.config={"code":{"copyTitle":"复制到剪贴板","maxShownLines":200},"comment":{},"math":{"delimiters":[{"display":true,"left":"$$","right":"$$"},{"display":true,"left":"\\[","right":"\\]"},{"display":false,"left":"$","right":"$"},{"display":false,"left":"\\(","right":"\\)"}],"strict":false},"search":{"highlightTag":"em","lunrIndexURL":"/index.json","lunrLanguageCode":"zh","lunrSegmentitURL":"/lib/lunr/lunr.segmentit.js","maxResultLength":100,"noResultsFound":"没有找到结果","snippetLength":50,"type":"lunr"}};</script><script src="/js/theme.min.js"></script></body></html>
